package dynamicProgramming.SingleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/21 08:02
 **/

import java.util.HashMap;
import java.util.Map;

/**
 * 题目 ：最长斐波那契数列
 * 题目详述 ：
 * 如果序列X_1, X_2, ..., X_n满足下列条件，就说它是斐波那契式的：
 * n >= 3
 * 对于所有i + 2 <= n，都有X_i + X_{i+1} = X_{i+2}
 * 给定一个严格递增的正整数数组形成序列 arr，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回0 。
 *
 * 提示：
 * 3 <= arr.length <= 1000
 * 1 <= arr[i] < arr[i + 1] <= 10^9
 */
public class LenLongestFibSubseq {
    /**
     * 思路 ：
     * 由于该问题需要求解的是 最长斐波那契数列（即，求解斐波那契数列的最优解）
     * （1）确定状态转移方程 ：
     * 假设f(i,j)为以arr[i]为结尾，同时又以arr[j]为倒数第二个元素的斐波那契数列;
     * 若是前面存在k,满足 arr[i] = arr[j] + arr[k]的话，
     * ===》 可以获取到状态转移方程 ：f(i , j) = f(j , k) + 1;
     * @param arr
     * @return
     */
    public int lenLongestFibSubseq(int[] arr) {
        // 使用哈希表，以O（1）的时间复杂度，实现查找某个数字在arr数组中的下标;
        Map<Integer , Integer> map = new HashMap<>();
        for(int i = 0 ; i < arr.length ; i++){
            // 即，以数组元素值为哈希表key，同时以其数组下标为哈希表value;
            // ===》 即，若是使用哈希表的话，可以使用时间复杂度为O（1）的方法，查找到数组中某个元素所对应的数组下标;
            map.put(arr[i] , i);
        }

        // 使用二维数组temp，temp[i][j]用来存储(以arr[i]为结尾，以arr[j]为倒数第二个元素的斐波那契数列);
        int[][] temp = new int[arr.length][arr.length];

        int result = 0;
        // 双层for循环遍历 ：遍历所有可能的斐波那契数列（即，以arr[i]为结尾，以arr[j]为倒数第二个元素的斐波那契数列）
        for(int i = 1 ; i < arr.length ; i++){
            for(int j = 0 ; j < i ; j++){
                // 若是arr[i] - arr[j]在map中存在的话，即直接返回其存储在哈希表中的数组下标;
                Integer k = map.getOrDefault(arr[i] - arr[j], -1);
                // 当k值取值范围[0 , j)时，即键为k的元素，存在于数组中;
                // 需要注意的是，temp[j][k]必然在之前for循环中求解过 && 同时temp[j][k]值也被保存到temp数组中;
                // 此处需要，将temp[i][j]存储下来，目的是为了后续更好地求解;
                temp[i][j] = k >= 0 && k < j ? temp[j][k] + 1 : 2;
                result = Math.max(result , temp[i][j]);
            }
        }
        return result > 2 ? result : 0;
    }
    /**
     * 分析 ：
     * （1）时间复杂度 ：双层for循环===》O（n*n）;
     * （2）空间复杂度 ：O（n）的哈希表 + O（n * n）的二维数组
     */
}
